package algorithm.middle;

import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-05-02 16:24
 * @Description:
 */
public class LeastBricks554 {
    /**
     * 题目要求穿过的砖块数量最少，等效于通过的间隙最多。
     *
     * 我们可以使用「哈希表」记录每个间隙的出现次数，最终统计所有行中哪些间隙出现得最多，
     * 使用「总行数」减去「间隙出现的最多次数」即是答案。
     *
     * 如何记录间隙呢？直接使用行前缀记录即可。
     *
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/brick-wall/solution/gong-shui-san-xie-zheng-nan-ze-fan-shi-y-gsri/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int leastBricks(List<List<Integer>> wall) {
        //key-缝隙位置 ，value-缝隙出现次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (List<Integer> list:wall){
            int count = 0;
            for (int i=0;i<list.size()-1;i++){
                //count代表缝隙位置
                count = count + list.get(i);
                map.put(count,map.getOrDefault(count,0)+1);
            }
        }
        int max = 0;
        for (Integer x:map.values()){
            max = Math.max(max,x);
        }
        return wall.size()-max;
    }
}
